The ever expanding use of the public Internet and private Intranet has meant a greater emphasis on improving functionality, performance, and quality of service in packet processing and in particular IP packet processing for digital communications. One critical aspect involved in achieving improved performance relates to datapath processing at each network node through which the path extends. This processing, as will be known to one skilled in the art, relates to multiple operations performed on the packets traversing each network node. These operations comprise the physical implementation of many services including, but not limited to, packet header verification according to protocol specification, packet classification according to service policies, packet modification according to selected services, packet queuing according to quality of service (QOS) policy, etc.
Traditionally, IP packet processing has been implemented utilizing one of two datapath architectures. These two architectures are packet-based datapath and flow-based datapath. In a flow-based datapath architecture, information which is searched, retrieved or calculated during the processing of the initial packet of a flow is cached for reuse during processing of subsequent packets of the same flow. Packet-based datapath architectures, on the other hand, treat each packet independently.
Flow-based datapath architectures are known in such implementations as NetFlow service acceleration used by Cisco systems and by Caspian Network's flow-based routing schemes.
Typically, a flow-based datapath builds a flow table, an entry in the flow table being a flow control block (FCB), for capturing essential elements of a flow. This happens either during the processing of the first packet of a flow appearing at the flow-based datapath or as a result of a control plane command issued before the first flow packet is encountered. When a packet is received at the node, the packet is associated with a FCB, and the FCB is retrieved from memory and used to grant the packet all required services with minimal additional accesses to memory. As will be apparent, this minimizes processor stalls by reducing memory accesses, accelerates packet processing, improves router/switch throughput and reduces cross-network delay.
A flow-based datapath model, as shown in FIG. 1, includes a Path Selector (PS), a Packet Path (PP) for the processing of the first packet of a flow in a manner almost identical to a packet-based datapath and a Flow Path (FP) for processing of subsequent packets of a flow.
The Path Selector is the first processing stage in a flow-based datapath. The Path Selector attempts to associate an ingress packet with an existing Flow Control Block. If an associated FCB exists in the Exact Match Flow Table (EMFT) the Path Selector relays the packet and the FCB ID to the Flow Path. Otherwise, the Path Selector relays the packet to the Packet Path. Associating a packet with a FCB entry could be achieved by performing an exact match lookup, such as a hash lookup, in the EMFT.
The Packet Path (PP) processes all packets independently. The example Packet Path shown in FIG. 2 implements four services. Each of the services is implemented in two stages: a classification stage “Cx” and a service stage “Sx”. The classification stage determines if a packet should be afforded the corresponding service by using a classification rule database, “Cx DB”. The service stage renders the service on the deserving packets using a service parameter database, “Sx DB”. The example shows an extreme case where all the classification and the service parameter databases are separate. In practice, these databases are combined as much as possible to reduce memory bandwidth overhead and packet latency. However, in most instances the individual SxDBs are kept separate because there is unlikely to be a one-to-one service policy correspondence. One such example is a module that includes an IPv4 forwarding service and a symmetric NAT (Network Address Translation) service. Each of these services maintains a separate SxDB. The IPv4 FIB (Forwarding Information Base) uses a longest matching prefix search algorithm and the symmetric NAT database use an exact match table, such as a hash table. During packet processing, the PP creates a flow profile. The flow profile describes all the services that were afforded to the packet and includes all the parameters needed for these services.
The Flow Path (FP) receives an ingress packet and an FCB identifier from the Path Selector. The FP uses the FCB associated with a packet to process the packet. In an ideal case, the FCB is the only entity retrieved by the FP from memory to process the packet. The FCB contains all required service parameters for packet processing, such as next-hop information, packet modification information, flow packet counters, flow state, etc. The flow state would be used to afford services that require stateful inspection, such as NAT. The Flow Path updates the timestamp that indicates when the last packet was received and the new dynamic flow state in the FCB. This timestamp is used for aging the FCB entry if the flow is inactive for a configurable period of time that is referred to as the flow timeout value. FIG. 3 shows an example abstraction of a FP.
The Flow-Based Datapath model has several limitations. One major limitation is that every traffic flow requires a FCB regardless of how many memory accesses are needed to process the packets in the packet path and regardless of the expected number of packets in the flow. This limitation imposes hard memory requirements on high-throughput Flow-Based Datapaths without efficiently trading the increased memory requirements for processing gains. For example, Internet traffic measurements under steady state traffic conditions show that on a 10 Gbps line, one would normally observe more than 2 million active flows using a flow timeout value of 15 seconds. DOS (Denial of Service) attacks utilizing the entire 10 Gbps with 24 million packets per second could raise the number of flows to a theoretical maximum of 360 million. For an FCB table of 4 million entries and assuming that each FCB on a service-rich datapath requires 128 bytes of storage, then a whopping 512 Mbytes of memory is needed for the FCB table alone. For this reason, as the number of active flows expected in a datapath increases, the storage requirements of the Flow Table data structure becomes extremely large which makes the pure Flow-Based Datapath architecture virtually unworkable.
Another limitation of the pure Flow-Based Datapath is the FCB creation overhead that is incurred on every flow regardless of the flow nature. This overhead may outweigh the advantages of flow-based processing for flows with a small number of packets.